#include "Sort.h"
#include "Stack.cpp"

void ArrayPrint(int* array, int arraySize) {
    for(int i = 0; i < arraySize; i++) {
        printf("%d ", array[i]);
    }   printf("\n");
}

void InsertSort(int* array, int arraySize) { // 直接插入排序
    assert(array);   int end, insert;
    for(int i = 0; i < (arraySize - 1); i++) {
        end = i;   // i = 当前有序序列的最后元素的位序
        insert = array[end + 1];  // temp = 要插入的元素
        while(end >= 0) {
            if(insert < array[end]) {
                array[end + 1] = array[end];
                --end;
            }
            else { break; }
        }   array[end + 1] = insert;
    }
}

void ShellSort(int* array, int arraySize) {  // 希尔排序
    assert(array);    int end, insert;
    int gap = arraySize;
    while(gap > 1) {
        gap = gap / 3 + 1; // +1保证了最后一次gap一定是1
        for(int i = 0; i + gap <= arraySize - 1; ++i) {
            // (i + gap)为要插入的元素的位序，要有效
            end = i; // i = 当前组中有序序列的最后元素的位序
            insert = array[end + gap];
            while(end >= 0) {
                if(insert < array[end]) {
                    array[end + gap] = array[end];
                    end -= gap;
                }
                else { break; }
            }   array[end + gap] = insert;
        }
        ArrayPrint(array, arraySize);
    }
}

void SelectSort(int* array, int arraySize) { // 直接选择排序
    assert(array);    int begin = 0;
    int end = arraySize - 1;
    while(begin < end) {
        int mini = begin;
        int maxi = end;
        for(int i = begin; i <= end; i++) {
            if(array[i] < array[mini]) mini = i;
            if(array[i] > array[maxi]) maxi = i;
        }
        Swap(&array[begin], &array[mini]);
        // 若max和bigin位置重叠，maxi位置需要修正
        if(begin == maxi) { maxi = mini; }
        Swap(&array[end], &array[maxi]);
        ++begin;  --end;
    }
}

void Swap(int* pnum1, int* pnum2) {
    int temp = *pnum1;   *pnum1 = *pnum2;   *pnum2 = temp;
}

void AdjustDown(int* array, int arraySize, int root) {
    int parent = root;
    int child = parent * 2 + 1;
    while(child < arraySize) {
        if(child + 1 < arraySize) {
            child = (array[child + 1] > array[child]) ? child + 1 : child;
        }
        if(array[child] > array[parent]) {
            Swap(&array[child], &array[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else { break; }
    }
}

void HeapSort(int* array, int arraySize) { // 堆排序
    // 排升序要建大堆
    for(int i = (arraySize - 1 - 1) / 2; i >= 0; --i) {
        AdjustDown(array, arraySize, i);
    }   int end = arraySize - 1;
    while(end > 0) {
        Swap(&array[0], &array[end]);
        AdjustDown(array, end, 0);
        --end;
    }
}

void BubbleSort(int* array, int arraySize) { // 冒泡排序
    for(int end = arraySize - 1; end > 0; --end) {
        int exchange = 0;
        for(int i = 1; i <= end; ++i) {
            if(array[i - 1] > array[i]) {
                Swap(&array[i - 1], &array[i]);
                exchange = 1;
            }
        }   if(!exchange)  break;
    }
}

/*
int FindPos(int* array, int begin, int end) { // 1. 左右指针法
    int midIndex = GetmidIndex(array, begin, end);
    Swap(&array[midIndex], &array[end]);
    int keyi = end;
    while(begin < end) {
        // begin找到比key大的元素就停止
        while(begin < end && array[begin] <= array[keyi]) { ++begin; }
        // end找到比key小的元素就停止
        while(begin < end && array[end] >= array[keyi]) { --end; }
        Swap(&array[begin], &array[end]);
    }   Swap(&array[begin], &array[keyi]);
    return begin;
}
*/

int GetmidIndex(int* array, int begin, int end) {
    int mid = (begin + end) / 2;
    if(array[begin] < array[mid]) {
        if(array[mid] < array[end]) { return mid; }
        else if(array[begin] > array[end]) { return begin; }
        else return end;
    }
    else { // array[begin] > array[mid]
        if(array[mid] > array[end]) { return mid; }
        else if(array[begin] < array[end]) { return begin; }
        else return end;
    }
}

int FindPos2(int* array, int begin, int end) { // 2. 挖坑法
    int midIndex = GetmidIndex(array, begin, end);
    Swap(&array[midIndex], &array[end]);
    int key = array[end]; // end为第1个坑的位序
    while(begin < end) {
        // begin找到比key大的元素就停止
        while(begin < end && array[begin] <= key) { ++begin; }
        array[end] = array[begin]; // begin为新坑
        // end找到比key小的元素就停止
        while(begin < end && array[end] >= key) { --end; }
        array[begin] = array[end]; // end为新坑
    }   array[begin] = key;
    return begin;
}

int FindPos3(int* array, int begin, int end) { // 3. 快慢指针法
    int midIndex = GetmidIndex(array, begin, end);
    Swap(&array[midIndex], &array[end]);
    int keyi = end;
    int prev = begin - 1;  int cur = begin;
    while(cur < end) {
        if(array[cur] < array[keyi] && ++prev != cur) {
            Swap(&array[prev], &array[cur]);
        }   ++cur;
    }   Swap(&array[++prev], &array[keyi]);
    return prev;
}

void QuickSort(int* array, int left, int right) { // 快速排序
    assert(array);
    if(left >= right) { return; } // 无效区间
    if(left - right + 1 > 10) {
        int div = FindPos3(array, left, right);
        QuickSort(array, left, div - 1);
        QuickSort(array, div + 1, right);
    }
    else {
        InsertSort(array + left, right - left + 1);
    }
}

void QuickSortNonR(int* array, int left, int right) {
    Stack st;    StackInit(&st);       // 用栈模拟实现
    StackPush(&st, right);    StackPush(&st, left);
    while(!StackEmpty(&st)) {
        int begin = StackTop(&st);   StackPop(&st);
        int end = StackTop(&st);     StackPop(&st);
        // [begin , end]
        int div = FindPos3(array, begin, end);
        // [begin, div - 1] div [div + 1 , end]
        if(div + 1 < end) {
            StackPush(&st, end);
            StackPush(&st, div + 1);
        }
        if(begin < div - 1) {
            StackPush(&st, div - 1);
            StackPush(&st, begin);
        }
    }
}

/*
void QuickSort(int* array, int left, int right) { // 快速排序
    assert(array);
    if(left >= right) { return; } // 无效区间
    int begin = left;    int end = right;
    int midIndex = GetmidIndex(array, begin, end);
    Swap(&array[midIndex], &array[end]);
    int keyi = end;
    while(begin < end) {
        // begin找到比key大的元素就停止
        while(begin < end && array[begin] <= array[keyi]) { ++begin; }
        // end找到比key小的元素就停止
        while(begin < end && array[end] >= array[keyi]) { --end; }
        Swap(&array[begin], &array[end]);
    }   Swap(&array[begin], &array[keyi]);
    QuickSort(array, left, begin - 1);
    QuickSort(array, begin + 1, right);
}
*/

/* 
1.  若选最右边的值作为key，一定要让begin先走，这样可保证begin
    与end相遇位置上的元素一定比key大
    ( 原因 ) 最后一次交换到begin与end相遇前，begin停下来时要么与end相遇(元素值大于key)，此时找到key对应位置。
    要么碰到了大于key的元素，又因为已经最后一次交换了，所以此时begin与end之间都是比key大的元素，则end移动，与
    begin相遇
2.  若选最左边的值作为key，一定要让end先走，这样可保证begin与
    end相遇位置上的元素一定比key小
*/

// 时间复杂度: O(N * LogN)
void _MergeSort(int* array, int left, int right, int* temp) { 
    if(left >= right) { return; } // 区间有效性判断
    int mid = left + (right - left) / 2;
    // [left , mid] [mid + 1 , right] 有序就可合并，但现在没有序，用子问题解决
    _MergeSort(array, left, mid, temp);
    _MergeSort(array, mid + 1, right, temp);
    // [left , mid] [mid + 1, right] 有序 → 归并
    /* 
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = begin1;
    while(begin1 <= end1 && begin2 <= end2) {
        if(array[begin1] < array[begin2]) {
            temp[index++] = array[begin1++];
        } else {
            temp[index++] = array[begin2++];
        }
    } // 当遍历完其中一个区间，将另一个区间剩余的数据直接放到tmp的后面
    while(begin1 <= end1) { temp[index++] = array[begin1++]; }
    while(begin2 <= end2) { temp[index++] = array[begin2++]; }
    //归并完后，拷贝回原数组
    for(int i = left; i <= right; ++i) { array[i] = temp[i]; }
    */
   MergeArray(array, left, mid, mid + 1, right, temp);
}


void MergeSort(int* array, int arraySize) { // 归并排序
    assert(array);                          // 递归实现
    int* temp = (int*)malloc(sizeof(int) * arraySize);
    _MergeSort(array, 0, arraySize - 1, temp);
    free(temp);
}

void MergeArray(int* array, int begin1, int end1, int begin2, int end2, int* temp) {
    int index = begin1,  left = begin1,  right = end2;
    while(begin1 <= end1 && begin2 <= end2) {
        if(array[begin1] < array[begin2]) {
            temp[index++] = array[begin1++];
        } else {
            temp[index++] = array[begin2++];
        }
    } // 当遍历完其中一个区间，将另一个区间剩余的数据直接放到tmp的后面
    while(begin1 <= end1) { temp[index++] = array[begin1++]; }
    while(begin2 <= end2) { temp[index++] = array[begin2++]; }
    //归并完后，拷贝回原数组
    for(int i = left; i <= right; ++i) { array[i] = temp[i]; }
}

void MergeSortNonR(int* array, int arraySize) { // 非递归实现归并排序
    assert(array);
    int* temp = (int*)malloc(sizeof(int) * arraySize);
    for(int gap = 1;  gap < arraySize; gap *= 2) {
        // 为什么有效条件是gap < arraySize？对于[0 , 8]  arraySize = 9
        // {[0 , 0] [1 , 1]}  {[2 , 2] ... [7 , 7]}  {[8 , 8]}  gap = 1
        // {[0 , 1] [2 , 3]}  {[4 , 5] [6 ,7]} {[8 , 8]}  gap = 2
        // {[0 , 3] [4 , 7]}  {[8 , 8]}  gap = 4
        // {[0 , 7] [8 , 8]}  gap = 8 
        for(int i = 0; i < arraySize; i += 2 * gap) {
            // [i , i + gap -1] [i + gap , i + 2 * gap - 1]
            int begin1 = i,  end1 = i + gap - 1;
            int begin2 = i + gap,  end2 = i + 2*gap -1;
            // 1. 合并时只有第一组，就不需要合并
            if(begin2 >= arraySize) { break; }
            // 2. 合并时第二组只有部分数据
            if(end2 >= arraySize) { end2 = arraySize - 1; }
            MergeArray(array, begin1, end1, begin2, end2, temp);
        }
    }
}

void _MergeSortFile(const char* file1, const char * file2, const char* mergefile) {
    FILE* fout1 = fopen(file1, "r");   FILE* fout2 = fopen(file2, "r");
    FILE* fin = fopen(mergefile, "w");
    int num1, num2;
    int res1 = fscanf(fout1, "%d\n", &num1);
    int res2 = fscanf(fout2, "%d\n", &num2);
    while(res1 != EOF && res2 != EOF) {
        if(num1 < num2) { 
            fprintf(fin, "%d\n", num1);
            res1 = fscanf(fout1, "%d\n", &num1);
        } else { 
            fprintf(fin, "%d\n", num2);
            res2 = fscanf(fout2, "%d\n", &num2);
        }
    } 
    while(res1 != EOF){ 
        fprintf(fin, "%d\n", num1);
        res1 = fscanf(fout1, "%d\n", &num1);
    }
    while(res2 != EOF){ 
        fprintf(fin, "%d\n", num2);
        res2 = fscanf(fout2, "%d\n", &num2);
    }
    fclose(fout1);  fclose(fout2);  fclose(fin);
}

void MergeSortFile(const char* file) {
    FILE* fout = fopen(file, "r");
    if(!fout) { printf("打开文件失败\n");  exit(-1); }
    // 将源文件中的数据逐段取出，内排序后写入小文件
    int tempSize = 10, i = 0, num = 0, temp[10]; 
    char subFile[20]; // 暂存有序子序列的子文件名
    int file_i = 1;  
    while(fscanf(fout, "%d\n", &num) != EOF) {
        if(i < tempSize - 1) { temp[i++] = num; }
        else { // 所读数据长度达到tempSize，需排序处理并写入文件
            temp[i++] = num; 
            QuickSort(temp, 0, tempSize - 1);
            sprintf(subFile, "sub\\sub_sort%d.txt", file_i++);
            FILE* fin = fopen(subFile, "w");
            if(!fin) { printf("打开文件失败\n");  system("pause"); }
            for(int i = 0; i < tempSize; ++i) {
                fprintf(fin, "%d\n", temp[i]);
            }   fclose(fin);
            i = 0; // 将temp "归零"
            memset(temp, 0, sizeof(int) * tempSize);
        }   
    }
    // 利用互相归并到文件，实现整体有序
    int subFileNum = 10;
    char File1_Name[50] = "sub\\sub_sort1.txt"; // 已合并文件名
    char File2_Name[50] = "sub\\sub_sort2.txt"; // 新加文件名
    char mergeFileName[50] = "sub\\1";          // 正在合并文件名
    for(int i = 2; i <= subFileNum; ++i) {
        sprintf(File2_Name, "sub\\sub_sort%d.txt", i);
        sprintf(mergeFileName, "%s%d", mergeFileName, i);
        _MergeSortFile(File1_Name, File2_Name, mergeFileName); 
        sprintf(File1_Name, "%s", mergeFileName);
    }
    fclose(fout); // 关闭源文件
}

void CountSort(int* array, int arraySize) { // 计数排序
    assert(array);
    int min = array[0], max = array[0];
    for(int i = 0; i < arraySize; ++i) {
        if(array[i] > max) { max = array[i]; }
        if(array[i] < min) { min = array[i]; }
    }   // [0, 9] 有(9 - 0 + 1)个元素
    int range = max - min + 1; 
    int* counter = (int*)malloc(sizeof(int) * range);
    memset(counter, 0, sizeof(int) * range);
    for(int i = 0; i < arraySize; ++i) {
        counter[array[i] - min]++;
    }
    int index = 0;
    for(int j = 0; j < range; ++j) {
        while(counter[j]--) {
            array[index++] = j + min;
        }
    }
    free(counter);
} // 时间复杂度: O(N + range) || 空间复杂度: O(range)

